Escritura de expresiones ?, II
Más en general, si una expresión se aplica a varios argumentos y uno de ellos es a su vez una expresión no atómica, este argumento se debe poner entre paréntesis.
Así, E(FG)H denota (E(FG))H , o sea la aplicación de E a los argumentos FG y H, mientras que EFGH denotaría (((EF)G)H), es decir la aplicación de E a los tres argumentos F, G y H.
Representación de expresiones ? como árboles binarios
Una expresión ? se puede representar mediante su árbol binario de análisis sintáctico (sin paréntesis), cuyos nodos pueden ser de tipo ? (abstración), ? (áplicación) o variable (son las hojas)
Ejemplo:
(?x.?y.x y)(?u.v)z
(Gp:) ?
(Gp:) ?
(Gp:) x
(Gp:) y
(Gp:) ?
(Gp:) x
(Gp:) y
(Gp:) ?
(Gp:) ?
(Gp:) ?
(Gp:) v
(Gp:) u
(Gp:) z
Cálculo ?: Ambitos de variables
Mínima función ? que la contiene y en la que aparece como argumento.
Ejemplos
(?x.?y.x y)(?u.v)z
(?x.?y.x y)(?u.v)z
(?x.?y.x y)(?u.v)z Ámbito global
Es semejante al ámbito en un programa
Cálculo ?: Ambitos devariables, II
Si se sustituye en una expresión ? una variable cuyo ámbito no es global por otra nueva, la expresión resultante es equivalente
Ejemplo: ?x.zx es equivalente a ?y.zy, pero no es equivalente a ?x.yx ni a ?z.zx
Ámbitos de variables: Ejemplo
(?x.?z.x(?x.zx))x
(Gp:) ?
(Gp:) ?
(Gp:) x
(Gp:) z
(Gp:) ?
(Gp:) x
(Gp:) ?
(Gp:) ?
(Gp:) x
(Gp:) x
(Gp:) ?
(Gp:) z
(Gp:) x
Ambitos de variables: Ejemplo, II
En el ejemplo anterior la variable x tiene ámbitos anidados (el segundo está contenido en el primero, que a su vez lo está en el global), lo que dificulta la sustitución y la evaluación de expresiones.
La evaluación de expresiones y la sustitución de variables es más sencilla cuando no hay ámbitos anidados.
Al igual que en programación, conviene evitar los ámbitos anidados de variables sustituyéndolas por otras.
Expresiones simples
Una expresión ? es simple si cada variable aparece en un solo contexto
Esta condición es más fuerte que la exigencia de que no haya ámbitos anidados; es análoga a pedir que en un programa cada variable aparezca en un solo bloque.
Ejemplos:
(?x.?z.x ?x.z x) z no es simple
(?x.?u.x ?y.u y) z es simple
Expresiones simples, II
En cualquier expresión ? se pueden renombrar las variables de modo que la expresión resultante, equivalente a la inicial, sea simple
Para ello basta con sustituir desde los ámbitos más restringidos a los más amplios las variables con ámbitos múltiples por variables nuevas.
Ejemplo: (?x.?z.x ?x.z x) z ? (?x.?z.x ?y.z y) z ? (?x.?u.x ?y.u y) z
Evaluación de expresiones simples
Dentro de una expresión simple, la aplicación de una función ? a otra subexpresión se evalúa mediante sustitución, rodeando el argumento de paréntesis si es necesario.
Ejemplos:
(?x.?u.x ?y.u y) z ? ?u.z ?y.u y
(?x.?u.x ?y.u y) ?w.w ? ?u. (?w.w) ?y.u y
El resultado de la evaluación de una expresión simple puede no ser simple. Ejemplo:
(?x.(?y.x) x) ?u.u ? (?y.?u.u) ?u.u
Procedimiento de evaluación total de expresiones ?
Para evaluar una expresión se puede hacer repetidamente lo siguiente:
Simplificar
Evaluar una subexpresión que sea la aplicación de una función ? a otra expresión, sustituyendo la subexprésión evaluada por el resultado (incluyendo paréntesis alrededor si hace falta).
Procedimiento de evaluación total de expresiones ?: Ejemplo
(?x.(?u.x u) x) x ?
(?y.(?u.y u) y) x ?
(?u.x u) x ? x x
Otra forma de hacerlo:
(?x.(?u.x u) x) x ?
(?y.(?u.y u) y) x ?
(?y.y y) x ? x x
Ejercicios obligatorios
Evaluar lo más posible las siguientes expresiones:
[EVAL1] (?x.?y.x y) (?u.u u) v
[EVAL2] (?u.u) (?x.?y.x y) v
Pasar a forma simple las siguientes expresiones:
[SIMPL1] (?x.?y.x(?x.yx))(?u.uxu)x
[SIMPL2] ?x.?x.?x.xxx
EJERCICIO OPTATIVO
[EVAL LAMBDA] Escribir un programa que evalúe expresiones ? de la forma (?x.E)F.
No terminación de laevaluación total
El procedimiento de evaluación total de expresiones ? puede no terminar nunca.
Ejemplo:
(?x.xx)(?y.yy)
al evaluarla una vez da ella misma: (?y.yy)(?y.yy)
Cálculo ?: Reglas de equivalencia
Lo anterior justifica definir la evaluación como una regla de equivalencia.
Las siguientes reglas permiten obtener expresiones ? equivalentes a otras dadas:
Regla ?: Sustitución de variables por otras (en particular, la conversión en expresiones simples)
Regla ? (evaluación): Aplicación de funciones
Regla ? (concreción): Equivalencia de ?x.Ex con E si x no es una variable libre de E
Cálculo ?: Forma normal
Se dice que una expresión ? está en forma normal si no se le puede aplicar ninguna regla de evaluación o concreción.
Según hemos visto, hay expresiones ? que no son equivalentes a ninguna otra que esté en forma normal.
Forma normal, II
Hay expresiones ? equivalentes a otra en forma normal que admiten evaluaciones indefinidas de subexpresiones suyas.
Ejemplo: (?x.?y.x) u ((?v.v v) ?w.ww)
Si se evalúa primero el último paréntesis se obtiene una expresión equivalente a la inicial, y por lo tanto se puede continuar realizando la misma operación indefinidamente.
Si se evalúa la primera función ?, se obtiene ?y.u ((?v.vv) ?w.ww), y evaluando de nuevo la primera función ? se obtiene u, que está en forma normal.
Ejercicio obligatorio
[FNINF] Demostrar que la siguiente expresión ? admite infinitas evaluaciones consecutivas sin que se llegue a una forma normal, pero también se puede evaluar dando lugar a una forma normal:
(?a.?b.b) ((?x.y(x x)) (?u.v(u u)) ?w.w
Unicidad de la forma normal
Teorema de Church-Rosser: Si una expresión ? se puede transformar mediante aplicaciones sucesivas de reducciónes ?, ? y ? en dos expresiones en forma normal, éstas se pueden transformar una en la otra mediante transformaciones ?.
Teorema de Church-Rosser:Idea de la demostración
Si una expresión ? simple incluye dos aplicaciones de función que se pueden evaluar, el orden de evaluación de las mismas es indiferente.
Reducción a tres casos
Primer caso: Funciones con ámbitos disjuntos
((?x.xx)u)((?y.yy)v)
Teorema de Church-Rosser:Segundo caso
Una de las aplicaciones está contenida en el argumento de la otra:
(?x.xux)((?y.ywy)v) (?x.xux)(vwv)
((?y.ywy)v)u((?y.ywy)v) (vwv)u(vwv)
Teorema de Church-Rosser:Tercer caso
Una de las dos aplicaciones está conteni-da en el cuerpo de la función de la otra:
(?x.(((?y.yy)u))xxx)v (?x.((uu)xxx))v
((?y.yy)u)vvv (uu)vvv
Teorema de Church-Rosser:Caso general
Análogo a uno de los tres anteriores, con árboles arbitrarios en lugar de u, v, w y en lugar de los cuerpos de las funciones
Cálculo ?: Normalización
Teorema de normalización: Dada una expresión ?, si existe otra expresión en forma normal equivalente a ella, se puede obtener mediante evaluación total de izquierda a derecha, como sigue:
Si hay alguna subexpresión de la expresión dada que sea una función ? y a la que se le pueda aplicar evaluación o concreción, hacerlo sobre la primera de ellas.
Simplificar el resultado y repetir lo anterior sobre las expresiones resultantes mientras ello sea posible.
Potencia computacional del Cálculo ?
Se puede representar la lógica booleana y las operaciones aritméticas mediante expresiones ?
Idea de la demostración: Ver la hoja de problemas número 1
Forma de la representación:
T,F???; ?,?,?,????
0, S,P,N??? ? N???
Definición de funciones recursivas (+, *, …)
Recursividad en el Cálculo ?
Teorema del punto fijo (Turing): Para cada expresión E hay otra expresión F que verifica que EF ? F
Demostración: Tomamos
F ? (?x.E(xx))(?y.E(yy))
Evaluando la aplicación tenemos que
F ? E((?y.E(yy))(?y.E(yy))) ? EF
Recursividad en el Cálculo ?, II
Observación:
El punto fijo de Turing se calcula aplicando una función fija Y, llamada combinador de punto fijo de Turing, a la función cuyo punto fijo se quiere calcular.
Concretamente, F ? YE, donde
Y ? ?E.(?x.E(xx))(?y.E(yy))
YE habitualmente no tiene forma normal, pero YEH puede tenerla para algunas H
Definición de funciones recursivas en el Cálculo ?
Ejemplo: Suma
Definición recursiva primitiva habitual:
x+y = (x==0) ? y : ((x-1)+y)+1
La traducimos al Cálculo ? en forma de punto fijo:
+xy ? ? (Nx) y (S(+(Px) y))
+ ? ?x.?y.? (Nx) y (S(+(Px) y)) ?
? (?G.?x.?y.?(Nx)y(S(G(Px) y)))+
Definición de funciones recursivas en el Cálculo ?, II
La solución sería el punto fijo asociado:
+ ? YE ? Y(?G.?x.?y.?(Nx)y(S(G(Px)y)))
Si sustituimos Y por su valor obtenemos una expresión sin forma normal (cada evaluación la complica más)
Pero si aplicamos la expresión anterior a dos números como S(S0) y S(S0) se obtiene una expresión con forma normal: S(S(S(S(0))))
Cálculo de los valores de funciones recursivas en el Cálculo ?. Ejemplo
Cálculo de 2+2:
Se puede hacer mediante evaluación total partiendo de la expresión que representa 2+2, que es (YE)22, donde
Y ? ?F.(?u.Fuu)(?v.Fvv)
E ? ?G.?x.?y.?(Nx)y(S(G(Px)y))
2 ? …
es decir
(?F.(?u.F(uu))(?v.F(vv)))(?G.?x.?y.?(Nx)y(S(G(Px)y)))…
Cálculo de los valores de funciones recursivas en el Cálculo ?. Ejemplo
Sustituyendo a medias y evaluando,
+22 ? E+22 ? ?(N2)2(S(+(P2)2) ? S(+(P2)2) ? S(+12)
+12 ? E+12 ? ?(N1)2(S(+(P1)2) ? S(+(P1)2) ? S(+02)
+02 ? E+02 ? ?(N0)2(S(+(P0)2) ? 2
+12 ? S2 ? 3
+22 ? S3 ? 4
Ejercicios
Definir funciones en el Cálculo ? que representen las siguientes funciones:
[LRS] Suma de los n primeros números impares (obligatorio)
[LRP] Producto de dos números
[LRF] Factorial de un número
[LRC] Cociente por defecto de dos números
Mostrar el cálculo de la suma de los dos primeros números impares, 2*2, 3! y 5/2
Cálculo ?: Conclusión
El Cálculo ? es tan potente como el cálculo de funciones recursivas, es decir tan potente como las máquinas de Turing, como las gramáticas, etc
 Página anterior | Volver al principio del trabajo | Página siguiente  |